package test.examation;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 阿里 {
    public static void main(String[] args) {
        //m1();
//        m2();//不会，重点看
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1); //用优先队列进行优化，从大到小
        int a[]={1,2,3,4,5};
        int[] ints = Arrays.copyOf(a, 4);

    }

    private static void m1() {
        //有n个人，每人有对应的钱币，有m个房子，每个房子有对应的价值和舒适度。
        //每个人只能买一个房子，每个房子只能被一个人买，求最大的舒适度和。
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] money = new int[n]; // 每个人的金币
        for (int i = 0; i < n; i ++)
            money[i] = sc.nextInt();
        // 第一个维度是舒适度，第二个维度是价格
        int[][] house = new int[m][2];
        for (int i = 0; i < m; i++) {
            house[i][0] = sc.nextInt();
            house[i][1] = sc.nextInt();
        }
        Arrays.sort(house, (o1, o2) -> o1[1] - o2[1]); //house按价格升序排列
        Arrays.sort(money); // 钱少的人先选
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1); //用优先队列进行优化，从大到小
        long res = 0;       //这题要用long, 给的都是大数
        int index = 0;
        for (int i = 0; i < money.length; i ++){
            int cur_money = money[i];
            while (index < house.length && house[index][1] <= cur_money){
                queue.add(house[index][0]);
                index ++;
            }       //把当前能买的所有房子放进去
            int add = 0;
            if (!queue.isEmpty()){
                add = queue.poll();     //得到能买的房子中最大舒适度的房子
            }
            res += add;
        }
        System.out.println(res);
    }


    public static void m2() {
        //给定一个字符串，字符串只包含abcdef 6个字母，求满足下列规则的最长子序列：
        //1.a必须在c,e前，c必须在e前；             a  c  e
        //2.b必须在d,f前, d必须在f前;             b   d  f
        Scanner sc = new Scanner(System.in);
        char[] cs = sc.next().toCharArray();
        int len = cs.length;
        int l1 = 0, l2 = 0;
        char[] c1 = new char[len];
        char[] c2 = new char[len];
        for (char c : cs) {
            if (c == 'a' || c == 'c' || c == 'e') c1[l1++] = c;
            if (c == 'b' || c == 'd' || c == 'f') c2[l2++] = c;
        }
        System.out.println(LIS(c1, l1) + LIS(c2, l2));
    }

    public static int LIS(char[] arr, int len) {
        int[] dp = new int[arr.length];
        int res = 0;
        for (int i = 0; i < len; i++) {
            char num = arr[i];
            int l = 0, r = res;
            while (l < r) {
                int m = (l + r) / 2;
                if (dp[m] <= num) l = m + 1;
                else r = m;
            }
            dp[l] = num;
            if (l == res) res++;
        }
        return res;
    }

}